import java.util.*;

class Solution {
    List<String> combinations;
    public List<String> letterCombinations(String digits) {
        combinations = new ArrayList<String>();
        if(digits.length()==0)return combinations;
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('0', "");
            put('1', "");
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        ArrayDeque<Character> ans= new ArrayDeque<Character>();
        backtrack(digits,0,phoneMap,ans);
        return combinations;
    }
    void backtrack(String digits,int index,Map<Character, String> phoneMap,ArrayDeque<Character> ans){
        if(index==digits.length()){
            StringBuilder sb=new StringBuilder();
           for(char a:ans){
               sb.append(a);
           }
            combinations.add(sb.toString());
            return;
        }
        char target= digits.charAt(index);
        String letter= phoneMap.get(target);
        for(int i=0;i<letter.length();i++){
            ans.add(letter.charAt(i));
            backtrack(digits,index+1,phoneMap,ans);
            ans.removeLast();
        }

    }

}